class Solution {
public:
    int largestPalindrome(int n) {
        if (n == 1)
            return 9;
        long long max = pow(10, n) - 1;
        long long min = pow(10, n - 1);
        long long i, j;
        for (i = max; i >= min; i--) {
            long long sum = i, temp = i;
            while (temp) {
                sum = sum * 10 + temp % 10;
                temp /= 10;
            }
            for (j = max; j * j >= sum; --j)
                if (sum % j == 0)
                    return sum % 1337;
        }
        return n;
    }
};
